{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Jump Game IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minJumps"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #跳跃游戏 IV"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>arr</code>&nbsp;，你一开始在数组的第一个元素处（下标为 0）。</p>\n",
    "\n",
    "<p>每一步，你可以从下标&nbsp;<code>i</code>&nbsp;跳到下标&nbsp;<code>i + 1</code> 、<code>i - 1</code> 或者 <code>j</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>i + 1</code> 需满足：<code>i + 1 &lt; arr.length</code></li>\n",
    "\t<li><code>i - 1</code>&nbsp;需满足：<code>i - 1 &gt;= 0</code></li>\n",
    "\t<li><code>j</code>&nbsp;需满足：<code>arr[i] == arr[j]</code>&nbsp;且&nbsp;<code>i != j</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回到达数组最后一个元素的下标处所需的&nbsp;<strong>最少操作次数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>注意：任何时候你都不能跳到数组外面。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [100,-23,-23,404,100,23,23,23,3,404]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>那你需要跳跃 3 次，下标依次为 0 --&gt; 4 --&gt; 3 --&gt; 9 。下标 9 为数组的最后一个元素的下标。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [7]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>一开始就在最后一个元素处，所以你不需要跳跃。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [7,6,9,6,9,6,9,7]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>你可以直接从下标 0 处跳到下标 7 处，也就是数组的最后一个元素处。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "<meta charset=\"UTF-8\" />\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>8</sup>&nbsp;&lt;= arr[i] &lt;= 10<sup>8</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [jump-game-iv](https://leetcode.cn/problems/jump-game-iv/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [jump-game-iv](https://leetcode.cn/problems/jump-game-iv/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[100,-23,-23,404,100,23,23,23,3,404]', '[7]', '[7,6,9,6,9,6,9,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        len_n = len(arr)\n",
    "        if len_n <= 1: return 0\n",
    "\n",
    "        hash_map = {}\n",
    "        for i, num in enumerate(arr):\n",
    "            if num not in hash_map:\n",
    "                hash_map[num] = [i]\n",
    "            else:\n",
    "                hash_map[num].append(i)\n",
    "        \n",
    "        visited = [0] * len_n\n",
    "        visited[0] = 1\n",
    "        q = deque([(0, 0)])\n",
    "        while q:\n",
    "            index, k = q.popleft()\n",
    "            for nxt_index in [index-1, index+1] + hash_map[arr[index]]:\n",
    "                if 0 <= nxt_index<len_n and not visited[nxt_index]:\n",
    "                    if nxt_index == len_n-1: return k+1\n",
    "                    visited[nxt_index] = 1\n",
    "                    q.append((nxt_index, k+1))\n",
    "            hash_map[arr[index]] = []\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "        visted = [0] * n\n",
    "\n",
    "        hash_map = {}\n",
    "        for i, num in enumerate(arr):\n",
    "            if num in hash_map:\n",
    "                hash_map[num].append(i)\n",
    "            else:\n",
    "                hash_map[num] = [i]\n",
    "        \n",
    "        q = deque([(0, 0)])\n",
    "        visted[0] = 1\n",
    "        while q:\n",
    "            index, k = q.popleft()\n",
    "            for next_index in [index-1, index+1] + hash_map[arr[index]]:\n",
    "                if 0<=next_index<n and not visted[next_index]:\n",
    "                    if next_index == n-1: return k+1\n",
    "                    visted[next_index] = 1\n",
    "                    q.append([next_index, k+1])\n",
    "            hash_map[arr[index]] = []\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        d = {}\n",
    "        for i, num in enumerate(arr):\n",
    "            d.setdefault(num, []).append(i)\n",
    "\n",
    "        visited = [0]*len(arr)\n",
    "        cur_pos = {0}\n",
    "        step = 0\n",
    "\n",
    "        while True:\n",
    "            for i in cur_pos:\n",
    "                if i == len(arr)-1:\n",
    "                    return step\n",
    "                visited[i] = 1\n",
    "\n",
    "            next_pos = set()\n",
    "            for i in cur_pos:\n",
    "                for j in (i-1, i+1):\n",
    "                    if 0<=j<len(arr) and visited[j] == 0:\n",
    "                        next_pos.add(j)\n",
    "\n",
    "                    if arr[i] in d:\n",
    "                        for j in d.pop(arr[i]):\n",
    "                            if visited[j] == 0:\n",
    "                                next_pos.add(j)\n",
    "\n",
    "            step += 1\n",
    "            cur_pos = next_pos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        d = {}\n",
    "        for i, num in enumerate(arr):\n",
    "            d.setdefault(num, []).append(i)\n",
    "\n",
    "        cur_pos = {0}\n",
    "        visited = [0]*len(arr)\n",
    "        step = 0\n",
    "\n",
    "        while True:\n",
    "            for i in cur_pos:\n",
    "                if i == len(arr)-1:\n",
    "                    return step\n",
    "                visited[i] = 1\n",
    "\n",
    "            next_pos = set()\n",
    "            for i in cur_pos:\n",
    "                for j in (i-1, i+1):\n",
    "                    if 0<=j<len(arr) and visited[j] == 0:\n",
    "                        next_pos.add(j)\n",
    "\n",
    "                    if arr[i] in d:\n",
    "                        for j in d.pop(arr[i]):\n",
    "                            if visited[j] == 0:\n",
    "                                next_pos.add(j)\n",
    "\n",
    "            step += 1\n",
    "            cur_pos = next_pos\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        # BFS\n",
    "        if len(arr) == 1:\n",
    "            return 0\n",
    "        n = len(arr)\n",
    "        vis = [False] * n\n",
    "        vis[0] = True\n",
    "\n",
    "        mp = defaultdict(list)\n",
    "        for i, x in enumerate(arr):\n",
    "            mp[x].append(i)\n",
    "\n",
    "        res = 0\n",
    "        q = [0]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x in tmp:\n",
    "                if x == n - 1:\n",
    "                    return res\n",
    "                if x + 1 < n and not vis[x + 1]:\n",
    "                    q.append(x + 1)\n",
    "                    vis[x + 1] = True\n",
    "                if x - 1 >= 0 and not vis[x - 1]:\n",
    "                    q.append(x - 1)\n",
    "                    vis[x - 1] = True\n",
    "                for id in mp[arr[x]]:\n",
    "                    if not vis[id]:\n",
    "                        vis[id] = True\n",
    "                        q.append(id)\n",
    "                del mp[arr[x]]\n",
    "            res += 1\n",
    "        return -1\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def minJumps(self, arr: List[int]) -> int:\n",
    "#         idxSameValue = defaultdict(list)\n",
    "#         for i, a in enumerate(arr):\n",
    "#             idxSameValue[a].append(i)\n",
    "#         visitedIndex = set()\n",
    "#         # q = deque()\n",
    "#         # q.append([0, 0])\n",
    "#         q = [[0, 0]]\n",
    "#         visitedIndex.add(0)\n",
    "#         while q:\n",
    "#             idx, step = q.pop(0)\n",
    "#             if idx == len(arr) - 1:\n",
    "#                 return step\n",
    "#             v = arr[idx]\n",
    "#             step += 1\n",
    "#             for i in idxSameValue[v]:\n",
    "#                 if i not in visitedIndex:\n",
    "#                     visitedIndex.add(i)\n",
    "#                     q.append([i, step])\n",
    "#             del idxSameValue[v]\n",
    "#             if idx + 1 < len(arr) and (idx + 1) not in visitedIndex:\n",
    "#                 visitedIndex.add(idx + 1)\n",
    "#                 q.append([idx + 1, step])\n",
    "#             if idx - 1 >= 0 and (idx - 1) not in visitedIndex:\n",
    "#                 visitedIndex.add(idx - 1)\n",
    "#                 q.append([idx - 1, step])\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def minJumps(self, arr: List[int]) -> int:\n",
    "#         n = len(arr)\n",
    "#         # if n == 0 or n == 1:\n",
    "#         #     return 0\n",
    "\n",
    "#         numIdMap = collections.defaultdict(list)\n",
    "#         for i, num in enumerate(arr):\n",
    "#             numIdMap[num].append(i)\n",
    "\n",
    "#         visted = {0}\n",
    "#         q = [(int(0), int(0))]\n",
    "#         while q:\n",
    "#             i, step = q.pop(0)\n",
    "#             if i == n - 1:\n",
    "#                 return step\n",
    "\n",
    "#             v = arr[i]\n",
    "#             for j in numIdMap[v]:\n",
    "#                 if j not in visted:\n",
    "#                     visted.add(j)\n",
    "#                     q.append((j, step + 1))\n",
    "\n",
    "#             if v in numIdMap:\n",
    "#                 del numIdMap[v]\n",
    "\n",
    "#             if i + 1 < n and (i + 1) not in visted:\n",
    "#                 visted.add(i + 1)\n",
    "#                 q.append((i + 1, step + 1))\n",
    "#             if i - 1 >= 0 and (i - 1) not in visted:\n",
    "#                 visted.add(i - 1)\n",
    "#                 q.append((i - 1, step + 1))\n",
    "\n",
    "#         return 0\n",
    "#         # return step\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        partition = defaultdict(list)\n",
    "        for i, x in enumerate(arr):\n",
    "            partition[x].append(i)\n",
    "        \n",
    "        n = len(arr)\n",
    "        q = [0]\n",
    "        vis = [0] * n\n",
    "        vis[0] = 1\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            tmp, q = q, []\n",
    "            for i in tmp:\n",
    "                if i == n - 1:\n",
    "                    return cnt\n",
    "\n",
    "                for j in partition[arr[i]]:\n",
    "                    if not vis[j]:\n",
    "                        vis[j] = 1\n",
    "                        q.append(j)\n",
    "                partition[arr[i]].clear()\n",
    "                \n",
    "                if (j := i + 1) < n and not vis[j]:\n",
    "                    vis[j] = 1\n",
    "                    q.append(j)\n",
    "                if (j := i - 1) >= 0 and not vis[j]:\n",
    "                    vis[j] = 1\n",
    "                    q.append(j)\n",
    "            cnt += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        d = collections.defaultdict(list)\n",
    "        for i, n in enumerate(arr):\n",
    "            d[n].append(i)\n",
    "\n",
    "        visited = [0]*len(arr)\n",
    "        cur_pos = {0}\n",
    "        step = 0\n",
    "\n",
    "        while True:\n",
    "            for i in cur_pos:\n",
    "                if i == len(arr)-1:\n",
    "                    return step\n",
    "                visited[i] = 1\n",
    "\n",
    "            next_pos = set()\n",
    "            for i in cur_pos:\n",
    "                for j in (i-1, i+1):\n",
    "                    if 0<=j<len(arr) and visited[j] == 0:\n",
    "                        next_pos.add(j)\n",
    "\n",
    "                if arr[i] in d:\n",
    "                    for j in d.pop(arr[i]):\n",
    "                        if visited[j] == 0:\n",
    "                            next_pos.add(j)\n",
    "\n",
    "            cur_pos = next_pos\n",
    "            step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        if len(arr) <= 1:\n",
    "            return 0\n",
    "        if len(arr) == 2 or arr[0] == arr[-1]:\n",
    "            return 1\n",
    "        elif arr[-2] == arr[0]:\n",
    "            return 2\n",
    "        # new_arr = arr[:2]\n",
    "        # for num in arr[2:]:\n",
    "        #     if new_arr[-1] == new_arr[-2] == num:\n",
    "        #         continue\n",
    "        #     new_arr.append(num)\n",
    "        # arr = new_arr\n",
    "        n = len(arr)\n",
    "        # print(n)\n",
    "        g = defaultdict(list)\n",
    "        groups = defaultdict(list)\n",
    "        edges = []\n",
    "        for idx, group in enumerate(arr):\n",
    "            groups[group].append(idx)\n",
    "            \n",
    "        visited = [False] * n\n",
    "        distances = [float(\"inf\")] * n\n",
    "        pq = []\n",
    "        pq.append((0, -0, arr[0], 0))\n",
    "        while pq:\n",
    "            dis, _, group, begin = heapq.heappop(pq)\n",
    "            if visited[begin]: continue\n",
    "            # print(dis, group, begin)\n",
    "            if dis >= distances[-1]:\n",
    "                continue\n",
    "            nxt_dis = dis + 2\n",
    "            for node in groups[group]:\n",
    "                if visited[node]: continue\n",
    "                visited[node] = True\n",
    "                # print(node)\n",
    "                if node == begin:\n",
    "                    nxt_dis -= 1\n",
    "                    distances[node] = min(distances[node], dis)\n",
    "                else:\n",
    "                    distances[node] = min(distances[node], dis+1)\n",
    "                if node - 1 >= 0 and not visited[node-1] and arr[node-1] != group:\n",
    "                    heapq.heappush(pq, (nxt_dis, -(node-1), arr[node-1], node-1))\n",
    "                if node + 1 < n and not visited[node+1] and arr[node+1] != group:\n",
    "                    heapq.heappush(pq, (nxt_dis, -(node+1), arr[node+1], node+1))\n",
    "\n",
    "                if node == begin:\n",
    "                    nxt_dis += 1\n",
    "            groups.pop(group)\n",
    "        return distances[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minJumps(self, arr: List[int]) -> int:\n",
    "#         n = len(arr)\n",
    "#         d = dict()\n",
    "#         for i in range(n):\n",
    "#             d[arr[i]] = [i] + d.get(arr[i], [])\n",
    "#         # lst = [n - 1]\n",
    "#         lst = deque([0])\n",
    "#         step = [-1] * n\n",
    "#         # lst = [0]\n",
    "#         step[0] = 0\n",
    "#         while len(lst) > 0:\n",
    "#             # x = lst[0]\n",
    "#             # del lst[0]\n",
    "#             x = lst.popleft()\n",
    "#             stepNow = step[x]\n",
    "#             if step[n-1] >= 0:\n",
    "#                 return step[n-1]\n",
    "#             for i in d[arr[x]]:\n",
    "#                 if step[i] < 0:\n",
    "#                     lst.append(i)\n",
    "#                     step[i] = stepNow + 1\n",
    "#             d[arr[x]] = []\n",
    "#             if x + 1 < n and step[x+1] < 0:\n",
    "#                 lst.append(x+1)\n",
    "#                 step[x+1] = stepNow + 1\n",
    "#             if x - 1 >= 0 and step[x-1] < 0:\n",
    "#                 lst.append(x-1)\n",
    "#                 step[x-1] = stepNow + 1\n",
    "            \n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        mp = defaultdict(list)\n",
    "        for i, num in enumerate(arr):\n",
    "            mp[num].append(i)\n",
    "        dist = [inf] * n\n",
    "        d = deque([0])\n",
    "        dist[0] = 0\n",
    "        while len(d) > 0:\n",
    "            t = d.popleft()\n",
    "            step = dist[t]\n",
    "            if t == n - 1:\n",
    "                return step\n",
    "            for ne in mp[arr[t]]:\n",
    "                if dist[ne] == inf:\n",
    "                    d.append(ne)\n",
    "                    dist[ne] = step + 1\n",
    "            mp.pop(arr[t])\n",
    "            if dist[t + 1] == inf:\n",
    "                d.append(t + 1)\n",
    "                dist[t + 1] = step + 1\n",
    "            if t and dist[t - 1] == inf:\n",
    "                d.append(t - 1)\n",
    "                dist[t - 1] = step + 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minJumps(self, arr: List[int]) -> int:\n",
    "#         n = len(arr)\n",
    "#         d = dict()\n",
    "#         for i in range(n):\n",
    "#             d[arr[i]] = d.get(arr[i], []) + [i]\n",
    "#         lst = [n - 1]\n",
    "#         step = [-1] * n\n",
    "#         lst = [0]\n",
    "#         step[0] = 0\n",
    "#         while len(lst) > 0:\n",
    "#             x = lst[0]\n",
    "#             del lst[0]\n",
    "#             stepNow = step[x]\n",
    "#             for i in d[arr[x]]:\n",
    "#                 if step[i] < 0:\n",
    "#                     lst.append(i)\n",
    "#                     step[i] = stepNow + 1\n",
    "#             d[arr[x]] = []\n",
    "#             if x + 1 < n and step[x+1] < 0:\n",
    "#                 lst.append(x+1)\n",
    "#                 step[x+1] = stepNow + 1\n",
    "#             if x - 1 >= 0 and step[x-1] < 0:\n",
    "#                 lst.append(x-1)\n",
    "#                 step[x-1] = stepNow + 1\n",
    "#             if step[n-1] >= 0:\n",
    "#                 return step[n-1]\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        mp = defaultdict(list)\n",
    "        for i, num in enumerate(arr):\n",
    "            mp[num].append(i)\n",
    "        dist = [inf] * n\n",
    "        d = deque([0])\n",
    "        dist[0] = 0\n",
    "        while len(d) > 0:\n",
    "            t = d.popleft()\n",
    "            step = dist[t]\n",
    "            if t == n - 1:\n",
    "                return step\n",
    "            for ne in mp[arr[t]]:\n",
    "                if dist[ne] == inf:\n",
    "                    d.append(ne)\n",
    "                    dist[ne] = step + 1\n",
    "            mp.pop(arr[t])\n",
    "            if dist[t + 1] == inf:\n",
    "                d.append(t + 1)\n",
    "                dist[t + 1] = step + 1\n",
    "            if t and dist[t - 1] == inf:\n",
    "                d.append(t - 1)\n",
    "                dist[t - 1] = step + 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        if len(arr) == 1:\n",
    "            return 0\n",
    "        \n",
    "        if arr[0] == arr[-1]:\n",
    "            return 1\n",
    "        dic = collections.defaultdict(list)\n",
    "        for i, a in enumerate(arr):\n",
    "            dic[a].append(i)\n",
    "        visited = [False] * len(arr)       \n",
    "        queue = deque()\n",
    "        queue.append([0,0])\n",
    "        while queue:\n",
    "            index, step = queue.popleft()\n",
    "            visited[index] = True\n",
    "            if index == len(arr)-1:\n",
    "                return step\n",
    "            step += 1\n",
    "            value = arr[index]\n",
    "            for i in dic[value]:\n",
    "                if not visited[i]:\n",
    "                    queue.append([i,step])\n",
    "            del dic[value]\n",
    "            if index + 1<len(arr) and not visited[index+1]:\n",
    "                queue.append([index+1,step])\n",
    "            if index - 1 > -1 and not visited[index-1]:\n",
    "                queue.append([index-1,step])\n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    "        #return dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        hashmap = defaultdict(list)\n",
    "        for i, num in enumerate(arr):  # 可以改成倒序，最大的优先出队\n",
    "            hashmap[num].append(i)\n",
    "        dist = [inf] * n\n",
    "        d = deque([0])\n",
    "        dist[0] = 0\n",
    "        while len(d) > 0:\n",
    "            t = d.popleft()\n",
    "            step = dist[t]\n",
    "            if t == n-1:\n",
    "                return step\n",
    "            for ne in hashmap[arr[t]]:\n",
    "                if dist[ne] == inf:\n",
    "                    d.append(ne)\n",
    "                    dist[ne] = step + 1\n",
    "            hashmap.pop(arr[t])\n",
    "            if dist[t + 1] == inf:\n",
    "                d.append(t+1)\n",
    "                dist[t+1] = step + 1\n",
    "            if t and dist[t - 1] == inf:\n",
    "                d.append(t - 1)\n",
    "                dist[t - 1] = step + 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        hashmap = defaultdict(list)\n",
    "#        for i, num in enumerate(arr):  # 可以改成倒序，最大的优先出队\n",
    "#           hashmap[num].append(i)\n",
    "        for i in range(len(arr)-1, -1, -1):\n",
    "            hashmap[arr[i]].append(i)\n",
    "        dist = [inf] * n\n",
    "        d = deque([0])\n",
    "        dist[0] = 0\n",
    "        while len(d) > 0:\n",
    "            t = d.popleft()\n",
    "            step = dist[t]\n",
    "            if t == n-1:\n",
    "                return step\n",
    "            for ne in hashmap[arr[t]]:\n",
    "                if dist[ne] == inf:\n",
    "                    d.append(ne)\n",
    "                    dist[ne] = step + 1\n",
    "            hashmap.pop(arr[t])\n",
    "            if dist[t + 1] == inf:\n",
    "                d.append(t+1)\n",
    "                dist[t+1] = step + 1\n",
    "            if t and dist[t - 1] == inf:\n",
    "                d.append(t - 1)\n",
    "                dist[t - 1] = step + 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        mp = defaultdict(list)\n",
    "        for i, num in enumerate(arr):\n",
    "            mp[num].append(i)\n",
    "        dist = [inf] * n\n",
    "        d = deque([0])\n",
    "        dist[0] = 0\n",
    "        while len(d) > 0:\n",
    "            t = d.popleft()\n",
    "            step = dist[t]\n",
    "            if t == n - 1:\n",
    "                return step\n",
    "            for ne in mp[arr[t]]:\n",
    "                if dist[ne] == inf:\n",
    "                    d.append(ne)\n",
    "                    dist[ne] = step + 1\n",
    "            mp.pop(arr[t])\n",
    "            if dist[t + 1] == inf:\n",
    "                d.append(t + 1)\n",
    "                dist[t + 1] = step + 1\n",
    "            if t and dist[t - 1] == inf:\n",
    "                d.append(t - 1)\n",
    "                dist[t - 1] = step + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        successors = defaultdict(list)\n",
    "        for idx, ii in enumerate(arr):\n",
    "            successors[ii].append(idx)\n",
    "\n",
    "        # print(num2idxes, successors)\n",
    "        q = deque([0])\n",
    "        ans = 0\n",
    "        visited = [False] * len(arr)\n",
    "        visited[0] = True\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                # print(q)\n",
    "                u = q.popleft()\n",
    "                if u == len(arr) - 1:\n",
    "                    return ans\n",
    "                \n",
    "                for v in successors[arr[u]]:\n",
    "                    if visited[v]:\n",
    "                        continue\n",
    "                    \n",
    "                    visited[v] = True\n",
    "                    q.append(v)\n",
    "                \n",
    "                if arr[u] in successors:\n",
    "                    del successors[arr[u]]\n",
    "                \n",
    "                if u > 0 and not visited[u - 1]:\n",
    "                    visited[u - 1] = True\n",
    "                    q.append(u - 1)\n",
    "                if u < len(arr) - 1 and not visited[u + 1]:\n",
    "                    visited[u + 1] = True\n",
    "                    q.append(u + 1)\n",
    "\n",
    "            ans += 1\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        idx_map, steps=defaultdict(list),[len(arr)-1]*len(arr)\n",
    "        for i,num in enumerate(arr):\n",
    "            idx_map[num].append(i)\n",
    "        queue=deque([0])\n",
    "        steps[0]=0\n",
    "        while queue:\n",
    "            idx=queue.popleft()\n",
    "            if idx==len(arr)-1:\n",
    "                break\n",
    "            nxt_step = steps[idx]+1\n",
    "            idx_map[arr[idx]]+=[idx+1,idx-1] if idx else [idx+1]\n",
    "            while idx_map[arr[idx]]:\n",
    "                if steps[(other:=idx_map[arr[idx]].pop())]>nxt_step:\n",
    "                    steps[other]=nxt_step\n",
    "                    queue.append(other)\n",
    "        return steps[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minJumps(self, arr: List[int]) -> int:\r\n",
    "        if len(arr) == 1:\r\n",
    "            return 0\r\n",
    "        vis = [False] * len(arr)\r\n",
    "        mp = defaultdict(list)\r\n",
    "        for i,x in enumerate(arr):\r\n",
    "            mp[x].append(i) \r\n",
    "        q = deque([0])\r\n",
    "        vis[0] = True\r\n",
    "        res = 1\r\n",
    "        while len(q):\r\n",
    "            for i in range(len(q)):\r\n",
    "                v = q.popleft()\r\n",
    "                if v - 1 == len(arr) - 1 or v + 1 == len(arr) - 1:\r\n",
    "                    return res \r\n",
    "                if v - 1 >= 0 and not vis[v - 1]:\r\n",
    "                    vis[v - 1] = True\r\n",
    "                    q.append(v - 1)\r\n",
    "                if v + 1 < len(arr) and not vis[v + 1]:\r\n",
    "                    vis[v + 1] = True\r\n",
    "                    q.append(v + 1)\r\n",
    "                for id in mp[arr[v]]:\r\n",
    "                    if id == len(arr) - 1:\r\n",
    "                        return res \r\n",
    "                    if not vis[id]:\r\n",
    "                        vis[id] = True\r\n",
    "                        q.append(id)\r\n",
    "                del mp[arr[v]]\r\n",
    "            res += 1\r\n",
    "        return res \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        value_index = {}\n",
    "        for index, value in enumerate(arr):\n",
    "            if value not in value_index:\n",
    "                value_index[value] = []\n",
    "            value_index[value].append(index)\n",
    "        queue = collections.deque([(0, 0)]) # [(index, step), ...]\n",
    "        visited_nodes = set()\n",
    "        while queue:\n",
    "            node, step = queue.popleft()\n",
    "            if node == len(arr) - 1:\n",
    "                return step\n",
    "            if node in visited_nodes:\n",
    "                continue\n",
    "            visited_nodes.add(node)\n",
    "            neighbor_nodes = value_index.get(arr[node], [])\n",
    "            if node - 1 >= 0 and node - 1 not in neighbor_nodes:\n",
    "                queue.append((node - 1, step + 1))\n",
    "            if node + 1 < len(arr) and node + 1 not in neighbor_nodes:\n",
    "                queue.append((node + 1, step + 1))\n",
    "            for each_neighbor in neighbor_nodes:\n",
    "                queue.append((each_neighbor, step + 1))\n",
    "            value_index.pop(arr[node], None)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        for i in range(len(arr)):\n",
    "            g[arr[i]].append(i)\n",
    "        q = deque()\n",
    "        q.append((0,0))\n",
    "        mp = set()\n",
    "        mp.add(0)\n",
    "        n = len(arr)\n",
    "        while len(q):\n",
    "            i,d = q.popleft()\n",
    "            if i==n-1:\n",
    "                return d\n",
    "            x = arr[i]\n",
    "            if i+1 < n and (i+1) not in mp:\n",
    "                mp.add(i+1)\n",
    "                q.append((i+1,d+1))\n",
    "            if i-1 >= 0 and (i-1) not in mp:\n",
    "                mp.add(i-1)\n",
    "                q.append((i-1,d+1))\n",
    "            for ti in g[x]:\n",
    "                if ti not in mp:\n",
    "                    mp.add(ti)\n",
    "                    q.append((ti,d+1))\n",
    "            g[x]=[]\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        sim_index = {}\n",
    "        for i in range(n):\n",
    "            if arr[i] not in sim_index:\n",
    "                sim_index[arr[i]]=[]\n",
    "            sim_index[arr[i]].append(i)\n",
    "        rs = n-1\n",
    "        q = deque()\n",
    "        q.append([0,0])\n",
    "        visited = set()\n",
    "        total = 0\n",
    "        visited.add(0)\n",
    "        while len(q)>0:\n",
    "            s,step = q.popleft()\n",
    "            if s == n-1:\n",
    "                return step\n",
    "            step+=1\n",
    "            for i in sim_index[arr[s]]:\n",
    "                if i!=s and i not in visited:\n",
    "                    visited.add(i)\n",
    "                    q.append([i,step])\n",
    "            sim_index[arr[s]]=[]\n",
    "            if s<n-1 and s+1 not in visited:\n",
    "                visited.add(s+1)\n",
    "                q.append([s+1, step])\n",
    "            if s>0 and s-1 not in visited:\n",
    "                visited.add(s-1)\n",
    "                q.append([s-1, step])\n",
    "           \n",
    "        return rs\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def minJumps(self, arr: List[int]) -> int:\n",
    "#         idxSameValue = defaultdict(list)\n",
    "#         for i, a in enumerate(arr):\n",
    "#             idxSameValue[a].append(i)\n",
    "#         visitedIndex = set()\n",
    "#         q = deque()\n",
    "#         q.append([0, 0])\n",
    "#         visitedIndex.add(0)\n",
    "#         while q:\n",
    "#             idx, step = q.popleft()\n",
    "#             if idx == len(arr) - 1:\n",
    "#                 return step\n",
    "#             v = arr[idx]\n",
    "#             step += 1\n",
    "#             for i in idxSameValue[v]:\n",
    "#                 if i not in visitedIndex:\n",
    "#                     visitedIndex.add(i)\n",
    "#                     q.append([i, step])\n",
    "#             del idxSameValue[v]\n",
    "#             if idx + 1 < len(arr) and (idx + 1) not in visitedIndex:\n",
    "#                 visitedIndex.add(idx + 1)\n",
    "#                 q.append([idx+1, step])\n",
    "#             if idx - 1 >= 0 and (idx - 1) not in visitedIndex:\n",
    "#                 visitedIndex.add(idx - 1)\n",
    "#                 q.append([idx-1, step])\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/jump-game-iv/solutions/1220752/tiao-yue-you-xi-iv-by-leetcode-solution-zsix/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        idxSameValue = defaultdict(list)\n",
    "        for i in range(len(arr)):\n",
    "            idxSameValue[arr[i]].append(i)\n",
    "        visitedIndex = set()\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        visitedIndex.add(0)\n",
    "        step = 0 \n",
    "        while q:\n",
    "            n = len(q)\n",
    "            for i in range(n):\n",
    "                idx = q.popleft()\n",
    "                if idx == len(arr) - 1:\n",
    "                    return step\n",
    "                v = arr[idx]\n",
    "                #step += 1\n",
    "                for i in idxSameValue[v]:\n",
    "                    if i not in visitedIndex:\n",
    "                        if i == len(arr) - 1:\n",
    "                            return step + 1 \n",
    "                        visitedIndex.add(i)\n",
    "                        q.append(i)\n",
    "                del idxSameValue[v]\n",
    "                if idx + 1 < len(arr) and (idx + 1) not in visitedIndex:\n",
    "                    if idx + 1 == len(arr) + 1:\n",
    "                        return step + 1\n",
    "                    visitedIndex.add(idx + 1)\n",
    "                    q.append(idx+1)\n",
    "                if idx - 1 >= 0 and (idx - 1) not in visitedIndex:\n",
    "                    visitedIndex.add(idx - 1)\n",
    "                    q.append(idx-1)\n",
    "            step += 1 \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n == 1:\n",
    "            return 0  # 如果数组长度为1，不需要操作\n",
    "\n",
    "        # 构建一个字典，用于存储每个元素值对应的索引列表\n",
    "        element_indices = {}\n",
    "        for i in range(n):\n",
    "            if arr[i] not in element_indices:\n",
    "                element_indices[arr[i]] = []\n",
    "            element_indices[arr[i]].append(i)\n",
    "\n",
    "        # BFS 使用队列，每个元素为 (position, steps) 的元组，表示位置和到达该位置所需的步数\n",
    "        queue = deque([(0, 0)])  # 起始位置是0，步数为0\n",
    "        visited = set([0])  # 记录已访问过的位置\n",
    "\n",
    "        while queue:\n",
    "            position, steps = queue.popleft()\n",
    "\n",
    "            if position == n - 1:\n",
    "                return steps  # 如果到达最后一个元素，返回步数\n",
    "\n",
    "            # 跳跃到相同值的其他位置\n",
    "            for next_position in element_indices[arr[position]]:\n",
    "                if next_position not in visited:\n",
    "                    queue.append((next_position, steps + 1))\n",
    "                    visited.add(next_position)\n",
    "\n",
    "            element_indices[arr[position]] = []  # 清空相同值的位置列表，避免重复访问\n",
    "\n",
    "            # 向前和向后跳跃\n",
    "            if position - 1 >= 0 and position - 1 not in visited:\n",
    "                queue.append((position - 1, steps + 1))\n",
    "                visited.add(position - 1)\n",
    "\n",
    "            if position + 1 < n and position + 1 not in visited:\n",
    "                queue.append((position + 1, steps + 1))\n",
    "                visited.add(position + 1)\n",
    "\n",
    "        return -1  # 如果无法到达最后一个元素，返回-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        idxSameValue = defaultdict(list)\n",
    "        for idx,value in enumerate(arr):\n",
    "            idxSameValue[value].append(idx)\n",
    "        q = deque()\n",
    "        q.append([0,0]) #从下表0开始跳，此时是0步\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        while q:\n",
    "            idx,step = q.popleft()\n",
    "            if idx == len(arr) - 1:\n",
    "                return step\n",
    "            step +=1\n",
    "            for i in idxSameValue[arr[idx]]:\n",
    "                q.append([i,step])\n",
    "            del idxSameValue[arr[idx]]\n",
    "            if idx+1 <= len(arr) - 1 and (idx+1) not in visited:\n",
    "                visited.add(idx+1)\n",
    "                q.append([idx+1,step])\n",
    "            if idx-1 >= 0 and (idx-1) not in visited:\n",
    "                visited.add(idx-1)\n",
    "                q.append([idx-1,step])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        dict1 = defaultdict(list)\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            dict1[arr[i]].append(i)\n",
    "        visited = set()\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        step = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                if cur == n-1:\n",
    "                    return step\n",
    "                visited.add(cur)\n",
    "                val = arr[cur]\n",
    "\n",
    "                for nxt in dict1[val]:\n",
    "                    if nxt == cur:\n",
    "                        continue\n",
    "                    if nxt in visited:\n",
    "                        continue\n",
    "                    q.append(nxt)\n",
    "                \n",
    "                dict1.pop(val)\n",
    "\n",
    "                if cur - 1 >= 0 and cur-1 not in visited:\n",
    "                    q.append(cur-1)\n",
    "                if cur + 1 < n and cur+1 not in visited:\n",
    "                    q.append(cur+1)\n",
    "            \n",
    "            step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        idxSameValue = defaultdict(list)\n",
    "        for i, a in enumerate(arr):\n",
    "            idxSameValue[a].append(i)\n",
    "        visitedIndex = set()\n",
    "        q = deque()\n",
    "        q.append([0, 0])\n",
    "        visitedIndex.add(0)\n",
    "        while q:\n",
    "            idx, step = q.popleft()\n",
    "            if idx == len(arr) - 1:\n",
    "                return step\n",
    "            v = arr[idx]\n",
    "            step += 1\n",
    "            for i in idxSameValue[v]:\n",
    "                if i not in visitedIndex:\n",
    "                    visitedIndex.add(i)\n",
    "                    q.append([i, step])\n",
    "            del idxSameValue[v]\n",
    "            if idx + 1 < len(arr) and (idx + 1) not in visitedIndex:\n",
    "                visitedIndex.add(idx + 1)\n",
    "                q.append([idx+1, step])\n",
    "            if idx - 1 >= 0 and (idx - 1) not in visitedIndex:\n",
    "                visitedIndex.add(idx - 1)\n",
    "                q.append([idx-1, step])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        dict1 = defaultdict(list)\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            dict1[arr[i]].append(i)\n",
    "        visited = set()\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        step = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                if cur == n-1:\n",
    "                    return step\n",
    "                visited.add(cur)\n",
    "                val = arr[cur]\n",
    "\n",
    "                for nxt in dict1[val]:\n",
    "                    if nxt == cur:\n",
    "                        continue\n",
    "                    if nxt in visited:\n",
    "                        continue\n",
    "                    q.append(nxt)\n",
    "                \n",
    "                dict1.pop(val)\n",
    "\n",
    "                if cur - 1 >= 0 and cur-1 not in visited:\n",
    "                    q.append(cur-1)\n",
    "                if cur + 1 < n and cur+1 not in visited:\n",
    "                    q.append(cur+1)\n",
    "            \n",
    "            step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        # 记录相同值的节点index\n",
    "        idxSameValue = defaultdict(list)\n",
    "        for i, a in enumerate(arr):\n",
    "            idxSameValue[a].append(i)\n",
    "        print(idxSameValue)\n",
    "        used = set()\n",
    "        q = deque()\n",
    "        # q = [index, step]\n",
    "        q.append([0,0])\n",
    "        used.add(0)\n",
    "        while q:\n",
    "            idx, step = q.popleft()\n",
    "            # 递归终止\n",
    "            if idx == n - 1:\n",
    "                return step\n",
    "            # 跳跃到相同值的节点\n",
    "            v = arr[idx]\n",
    "            step += 1\n",
    "            for i in idxSameValue[v]:\n",
    "                if i not in used:\n",
    "                    used.add(i)\n",
    "                    q.append([i,step])\n",
    "            del idxSameValue[v]\n",
    "            if idx + 1 < len(arr) and (idx + 1) not in used:\n",
    "                used.add(idx + 1)\n",
    "                q.append([idx+1, step])\n",
    "            if idx - 1 >= 0 and (idx - 1) not in used:\n",
    "                used.add(idx - 1)\n",
    "                q.append([idx-1, step])\n",
    "            \n",
    "                \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        BFS\n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        hashTable = defaultdict(list)\n",
    "        for i,num in enumerate(arr):\n",
    "            hashTable[num].append(i)\n",
    "        que = queue.Queue()\n",
    "        que.put(0)\n",
    "        rs = 0\n",
    "        seen = set([0])\n",
    "        while que:\n",
    "            sz = que.qsize()\n",
    "            for i in range(sz):\n",
    "                idx = que.get()\n",
    "                if idx == n-1:\n",
    "                    return rs\n",
    "                for i in hashTable[arr[idx]]:\n",
    "                    if i not in seen:\n",
    "                        que.put(i)\n",
    "                        seen.add(i)\n",
    "                del hashTable[arr[idx]] #清空值 防止重复添加\n",
    "                if idx>0 and idx-1 not in seen:\n",
    "                    que.put(idx-1)\n",
    "                    seen.add(idx-1)\n",
    "                if idx+1<n and idx+1 not in seen:\n",
    "                    que.put(idx+1)\n",
    "                    seen.add(idx+1)\n",
    "            rs += 1\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n, dc, vis = len(arr), defaultdict(list), set()\n",
    "        has, dp, cnt = [False] + [True] * (n-1) + [False], [0], 0\n",
    "        def do(x):\n",
    "            if has[x]:\n",
    "                dp.append(x)\n",
    "                has[x] = False\n",
    "        for i in range(n): dc[arr[i]].append(i)\n",
    "        while has[-2]:\n",
    "            ndp, dp, cnt = dp, [], cnt + 1\n",
    "            for i in ndp:\n",
    "                if arr[i] not in vis:\n",
    "                    vis.add(arr[i])\n",
    "                    for j in dc[arr[i]]: do(j)\n",
    "                do(i+1)\n",
    "                do(i-1)\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        cluster = dict()\n",
    "        # 分好组\n",
    "        for i,x in enumerate(arr):\n",
    "            if x not in cluster:\n",
    "                cluster[x] = []\n",
    "            cluster[x].append(i)\n",
    "        \n",
    "        q = deque()\n",
    "        q.append((0, 0))\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur[0] == len(arr) - 1:\n",
    "                return cur[1]\n",
    "            if cur[0] - 1 >= 0 and cur[0] - 1 not in visited:\n",
    "                q.append((cur[0] - 1, cur[1] + 1))\n",
    "                visited.add(cur[0] - 1)\n",
    "            if cur[0] + 1 < len(arr) and cur[0] + 1 not in visited:\n",
    "                q.append((cur[0] + 1, cur[1] + 1))\n",
    "                visited.add(cur[0] + 1)\n",
    "            if arr[cur[0]] not in cluster:continue\n",
    "            for x in cluster[arr[cur[0]]]:\n",
    "                if x not in visited:\n",
    "                    q.append((x, cur[1] + 1))\n",
    "                    visited.add(x)\n",
    "            del cluster[arr[cur[0]]]\n",
    "        del visited\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import deque\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        # build graph\n",
    "        edges = {}\n",
    "        for idx, num in enumerate(arr):\n",
    "            if num not in edges:\n",
    "                edges[num] = []\n",
    "            edges[num].append(idx)\n",
    "        \n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        queue = deque()\n",
    "        queue.append((0, 0))\n",
    "        trgIdx = len(arr) - 1\n",
    "\n",
    "        while queue:\n",
    "            curIdx, curStep = queue.popleft()\n",
    "            if curIdx == trgIdx:\n",
    "                return curStep\n",
    "            curStep += 1\n",
    "            if (curIdx + 1) not in visited:\n",
    "                visited.add(curIdx + 1)\n",
    "                queue.append((curIdx + 1, curStep))\n",
    "            if (curIdx != 0) and (curIdx - 1) not in visited:\n",
    "                visited.add(curIdx - 1)\n",
    "                queue.append((curIdx - 1, curStep))\n",
    "            \n",
    "            curNum = arr[curIdx]\n",
    "            if curNum in edges:\n",
    "                for idx in edges[curNum]:\n",
    "                    if idx == curIdx:\n",
    "                        continue\n",
    "                    if idx not in visited:\n",
    "                        visited.add(idx)\n",
    "                        queue.append((idx, curStep))\n",
    "                edges.pop(curNum)\n",
    "        \n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        cluster = dict()\n",
    "        # 分好组\n",
    "        for i,x in enumerate(arr):\n",
    "            if x not in cluster:\n",
    "                cluster[x] = []\n",
    "            cluster[x].append(i)\n",
    "        \n",
    "        q = deque()\n",
    "        q.append((0, 0))\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        while q:\n",
    "            cur = q.popleft()\n",
    "            if cur[0] == len(arr) - 1:\n",
    "                return cur[1]\n",
    "            if cur[0] - 1 >= 0 and cur[0] - 1 not in visited:\n",
    "                q.append((cur[0] - 1, cur[1] + 1))\n",
    "                visited.add(cur[0] - 1)\n",
    "            if cur[0] + 1 < len(arr) and cur[0] + 1 not in visited:\n",
    "                q.append((cur[0] + 1, cur[1] + 1))\n",
    "                visited.add(cur[0] + 1)\n",
    "            if arr[cur[0]] not in cluster:continue\n",
    "            for x in cluster[arr[cur[0]]]:\n",
    "                if x not in visited:\n",
    "                    q.append((x, cur[1] + 1))\n",
    "                    visited.add(x)\n",
    "            del cluster[arr[cur[0]]]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        if len(arr) <= 1:\n",
    "            return 0\n",
    "        if len(arr) == 2 or arr[0] == arr[-1]:\n",
    "            return 1\n",
    "        elif arr[-2] == arr[0]:\n",
    "            return 2\n",
    "        # new_arr = arr[:2]\n",
    "        # for num in arr[2:]:\n",
    "        #     if new_arr[-1] == new_arr[-2] == num:\n",
    "        #         continue\n",
    "        #     new_arr.append(num)\n",
    "        # arr = new_arr\n",
    "        n = len(arr)\n",
    "        # print(n)\n",
    "        g = defaultdict(list)\n",
    "        groups = defaultdict(list)\n",
    "        edges = []\n",
    "        for idx, group in enumerate(arr):\n",
    "            groups[group].append(idx)\n",
    "            \n",
    "        visited = [False] * n\n",
    "        distances = [float(\"inf\")] * n\n",
    "        pq = []\n",
    "        pq.append((0, -0, arr[0], 0))\n",
    "        while pq:\n",
    "            dis, _, group, begin = heapq.heappop(pq)\n",
    "            if visited[begin]: continue\n",
    "            # print(dis, group, begin)\n",
    "            if dis >= distances[-1]:\n",
    "                continue\n",
    "            nxt_dis = dis + 2\n",
    "            for node in groups[group]:\n",
    "                if visited[node]: continue\n",
    "                visited[node] = True\n",
    "                # print(node)\n",
    "                if node == begin:\n",
    "                    nxt_dis -= 1\n",
    "                    distances[node] = min(distances[node], dis)\n",
    "                else:\n",
    "                    distances[node] = min(distances[node], dis+1)\n",
    "                if node - 1 >= 0 and not visited[node-1] and arr[node-1] != group:\n",
    "                    heapq.heappush(pq, (nxt_dis, -(node-1), arr[node-1], node-1))\n",
    "                if node + 1 < n and not visited[node+1] and arr[node+1] != group:\n",
    "                    heapq.heappush(pq, (nxt_dis, -(node+1), arr[node+1], node+1))\n",
    "\n",
    "                if node == begin:\n",
    "                    nxt_dis += 1\n",
    "            # groups.pop(group)\n",
    "        return distances[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        graph = collections.defaultdict(list)\n",
    "        for i, num in enumerate(arr):\n",
    "            graph[num].append(i) # val: [index of all vals]\n",
    "\n",
    "        queue = collections.deque()\n",
    "        queue.append([0, 0])\n",
    "        visited = set()\n",
    "        visited.add(0)\n",
    "        while queue:\n",
    "            node, step = queue.popleft()\n",
    "            if node == n -1:\n",
    "                return step\n",
    "            for nei in [node -1, node + 1] + graph[arr[node]]: # graph[node] not graph[num], arr[node] not node\n",
    "                # must have 0 <= nei < n. \n",
    "                if 0 <= nei < n and nei not in visited: #and node != nei optional\n",
    "                    queue.append([nei, step + 1])\n",
    "                    visited.add(nei)\n",
    "            del graph[arr[node]] # arr[node] not node\n",
    "        return step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n == 1: return 0\n",
    "        dct = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            dct[arr[i]].append(i)\n",
    "        visited = set()\n",
    "        q = deque([n-1])\n",
    "        res = 1\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                cur = q.popleft()\n",
    "                for u in dct[arr[cur]]:\n",
    "                    if u == 0:\n",
    "                        return res\n",
    "                    if u not in visited:\n",
    "                        q.append(u)\n",
    "                        visited.add(u)\n",
    "                if cur - 1 >= 0 and cur - 1 not in visited:\n",
    "                    if cur - 1 == 0:\n",
    "                        return res\n",
    "                    q.append(cur - 1)\n",
    "                    visited.add(cur-1)\n",
    "                if cur + 1 < n and cur + 1 not in visited:\n",
    "                    q.append(cur + 1)\n",
    "                    visited.add(cur+1)\n",
    "            res += 1\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "              "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        idxSameValue = defaultdict(list)\n",
    "        for i, a in enumerate(arr):\n",
    "            idxSameValue[a].append(i)\n",
    "        visitedIndex = set()\n",
    "        visitedValue = set()\n",
    "        q = deque()\n",
    "        q.append([0, 0])\n",
    "        visitedIndex.add(0)\n",
    "        while q:\n",
    "            idx, step = q.popleft()\n",
    "            if idx == len(arr) - 1:\n",
    "                return step\n",
    "            v = arr[idx]\n",
    "            step += 1\n",
    "            if v not in visitedValue:\n",
    "                visitedValue.add(v)\n",
    "                for i in idxSameValue[v]:\n",
    "                    if i not in visitedIndex:\n",
    "                        visitedIndex.add(i)\n",
    "                        q.append([i, step])\n",
    "            if idx + 1 < len(arr) and (idx + 1) not in visitedIndex:\n",
    "                visitedIndex.add(idx + 1)\n",
    "                q.append([idx+1, step])\n",
    "            if idx - 1 >= 0 and (idx - 1) not in visitedIndex:\n",
    "                visitedIndex.add(idx - 1)\n",
    "                q.append([idx-1, step])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        visit = {i: False for i in range(len(arr))}\n",
    "        val_dict = defaultdict(list)\n",
    "        for i in range(len(arr)):\n",
    "            val_dict[arr[i]].append(i)\n",
    "\n",
    "        q = [(0, 0)]\n",
    "        while q:\n",
    "            cur_step, cur_ind = heapq.heappop(q)\n",
    "            if cur_ind == len(arr) - 1:\n",
    "                return cur_step\n",
    "            visit[cur_ind] = True\n",
    "            if 0 <= cur_ind+1 < len(arr) and not visit[cur_ind+1]:\n",
    "                heapq.heappush(q, (cur_step+1, cur_ind+1))\n",
    "            if 0 <= cur_ind-1 < len(arr) and not visit[cur_ind-1]:\n",
    "                heapq.heappush(q, (cur_step+1, cur_ind-1))\n",
    "            for ind in val_dict[arr[cur_ind]]:\n",
    "                if ind != cur_ind and not visit[ind]:\n",
    "                    heapq.heappush(q, (cur_step+1, ind))\n",
    "            del val_dict[arr[cur_ind]]\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        cnt = -1\n",
    "        dq = deque([0])\n",
    "        visited = set([0])\n",
    "        visitedval = set()\n",
    "        d = defaultdict(list)\n",
    "        for n, i in enumerate(arr):\n",
    "            d[i].append(n)\n",
    "        while dq:\n",
    "            cnt += 1\n",
    "            for _ in range(len(dq)):\n",
    "                cur = dq.popleft()\n",
    "\n",
    "                if cur == len(arr)-1:\n",
    "                    return cnt\n",
    "\n",
    "                if cur+1 != len(arr) and not cur+1 in visited:\n",
    "                    visited.add(cur+1)\n",
    "                    dq.append(cur+1)\n",
    "                if cur-1 != -1  and not cur-1 in visited:\n",
    "                    visited.add(cur-1)\n",
    "                    dq.append(cur-1)\n",
    "                if not arr[cur] in visitedval:\n",
    "                    for j in d[arr[cur]]:\n",
    "                        if not j in visited:\n",
    "                            visited.add(j)\n",
    "                            dq.append(j)\n",
    "                    visitedval.add(arr[cur])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        idx={}\n",
    "        cache=[float('inf')]*len(arr)\n",
    "        visited=set()\n",
    "        v_visited=set()\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] in idx:\n",
    "                idx[arr[i]].append(i)\n",
    "            else:\n",
    "                idx[arr[i]] = [i]\n",
    "        q = []\n",
    "        q.append(0)\n",
    "        depth=0\n",
    "        while len(q) > 0:\n",
    "            tmp = len(q)\n",
    "            for k in range(tmp):\n",
    "                i = q[k]\n",
    "                if i==len(arr)-1:\n",
    "                    return depth\n",
    "                if i+1 not in visited and i<len(arr)-1:\n",
    "                    q.append(i+1)\n",
    "                    visited.add(i+1)\n",
    "                if i-1 not in visited and i > 0:\n",
    "                    q.append(i-1)\n",
    "                    visited.add(i-1)\n",
    "                idxs = idx[arr[i]]\n",
    "                if arr[i] in v_visited:\n",
    "                    continue\n",
    "                for j in range(len(idxs)):\n",
    "                    p = idxs[j]\n",
    "                    v_visited.add(arr[p])\n",
    "                    if p not in visited:\n",
    "                        q.append(p)\n",
    "                        visited.add(p)\n",
    "                        v_visited.add(arr[p])\n",
    "                \n",
    "            q=q[tmp:]\n",
    "            depth+=1\n",
    "            \n",
    "        return cache[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        cur = [0]\n",
    "        pos = defaultdict(list)\n",
    "        for i, a in enumerate(arr):\n",
    "            pos[a].append(i)\n",
    "        visited = set([0])\n",
    "        valuevisied = set()\n",
    "        dis = 0\n",
    "        n  = len(arr)\n",
    "        while cur:\n",
    "            next = []\n",
    "            for i in cur:\n",
    "                if i == n-1:\n",
    "                    return dis\n",
    "                if i > 0 and i-1 not in visited:\n",
    "                    next.append(i-1)\n",
    "                    visited.add(i-1)\n",
    "                if i < n-1 and i+1 not in visited:\n",
    "                    next.append(i+1)\n",
    "                    visited.add(i+1)\n",
    "                if arr[i] not in valuevisied:\n",
    "                    valuevisied.add(arr[i])\n",
    "                    for eq in pos[arr[i]]:\n",
    "                        if eq not in visited:\n",
    "                            next.append(eq)\n",
    "                            visited.add(eq)\n",
    "            dis += 1\n",
    "            cur = next\n",
    "        return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr):\n",
    "        \"\"\"\n",
    "        从起点位置跳转到最后一个节点所需要的最少的步骤数\n",
    "        Args:   \n",
    "            arr (list[int]):\n",
    "        returns (int):\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if arr == None or len(arr) < 2:\n",
    "            return 0 \n",
    "\n",
    "        n = len(arr)\n",
    "        num_pos_dict = collections.defaultdict(list)   #key: 数组中的数值, value: 该数值在数组中所处的位置\n",
    "\n",
    "        #统计数组之中各个不同的数值位于的位置\n",
    "        for idx, num in enumerate(arr):\n",
    "            num_pos_dict[num].append(idx)\n",
    "\n",
    "        print(f\"初始化后的dict{num_pos_dict}\")\n",
    "        distance = [float('inf') for _ in range(n)] #从0位置到达各个位置所需要的最少的跳数\n",
    "        distance[0] = 0\n",
    "\n",
    "        queue = collections.deque()\n",
    "        queue.append(0) #从0节点开始出发\n",
    "\n",
    "        #使用bfs计算最短步骤数\n",
    "        while queue:\n",
    "            cur_node = queue.popleft()\n",
    "            step = distance[cur_node]   #跳跃到该节点所需要的最少的跳数\n",
    "\n",
    "            #若当前节点恰好是最终节点, 直接return\n",
    "            if cur_node == n - 1:\n",
    "                return step \n",
    "            \n",
    "            #从该节点跳到相同元素值的位置\n",
    "            for neighbor_node in num_pos_dict[arr[cur_node]]:\n",
    "                if distance[neighbor_node] == float('inf'):\n",
    "                    distance[neighbor_node] = step + 1\n",
    "                    queue.append(neighbor_node)\n",
    "            \n",
    "            #为了避免再次重复遍历该相同元素的邻接节点, 将其从字典之中删除\n",
    "            del num_pos_dict[arr[cur_node]]\n",
    "\n",
    "            #从cur_node向前移动, 若该节点未被访问过, 记录下该节点的最短跳数\n",
    "            if cur_node != n - 1 and distance[cur_node + 1] == float('inf'):\n",
    "                distance[cur_node + 1] = step + 1\n",
    "                queue.append(cur_node + 1)\n",
    "\n",
    "            #从cur_node向后移动\n",
    "            if cur_node != 0 and distance[cur_node - 1] == float('inf'):\n",
    "                distance[cur_node - 1] = step + 1\n",
    "                queue.append(cur_node - 1)\n",
    "        \n",
    "        return -1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        #bfs\n",
    "        same = {}\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            if arr[i] not in same:\n",
    "                same[arr[i]] = [i]\n",
    "            else:\n",
    "                same[arr[i]].append(i)\n",
    "        \n",
    "        queue = [(0, 0)]\n",
    "        s = 0\n",
    "        searched = set([0])\n",
    "        while s < len(queue):\n",
    "            x, steps = queue[s]\n",
    "            if x + 1 < n and x + 1 not in searched:\n",
    "                searched.add(x + 1)\n",
    "                queue.append((x + 1, steps + 1))\n",
    "                if x + 1 == n - 1:\n",
    "                    return steps + 1\n",
    "            if x - 1 >= 0 and x - 1 not in searched:\n",
    "                searched.add(x - 1)\n",
    "                queue.append((x-1, steps + 1))\n",
    "            if arr[x] in same:\n",
    "                for y in same[arr[x]]:\n",
    "                    if y != x and y not in searched:\n",
    "                        searched.add(y)\n",
    "                        queue.append((y, steps + 1))\n",
    "                        if y == n - 1:\n",
    "                            return steps + 1\n",
    "                same.pop(arr[x])\n",
    "            s += 1\n",
    "        return n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        d = collections.defaultdict(list)\n",
    "        mark = collections.defaultdict(int)\n",
    "        for pos, a in enumerate(arr):\n",
    "            d[a].append(pos)\n",
    "            mark[a] = 0\n",
    "        q = collections.deque()\n",
    "        n = len(arr)\n",
    "        dp = [-1] * n\n",
    "        dp[-1] = 0\n",
    "        q.append(n-1)\n",
    "        while q:\n",
    "            p = q.popleft()\n",
    "            num = arr[p]\n",
    "            jump = dp[p]\n",
    "            if mark[num] == 0:\n",
    "                for pos in d[num]:\n",
    "                    if pos != p and dp[pos] == -1:\n",
    "                        dp[pos] = jump + 1\n",
    "                        q.append(pos)\n",
    "                mark[num] = 1\n",
    "                    # else:\n",
    "                    #     if jump + 1 < dp[pos]:\n",
    "                    #         dp[pos] = jump + 1\n",
    "                    #         q.append(pos)\n",
    "            if p < n - 1:\n",
    "                pos = p + 1\n",
    "                if dp[pos] == -1:\n",
    "                    dp[pos] = jump + 1\n",
    "                    q.append(pos)\n",
    "            if p > 0:\n",
    "                pos = p - 1\n",
    "                if dp[pos] == -1:\n",
    "                    dp[pos] = jump + 1\n",
    "                    q.append(pos)\n",
    "        # print(d)\n",
    "        return dp[0]\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for idx, num in enumerate(arr):\n",
    "            d[num].append(idx)\n",
    "        visited = {0}\n",
    "        queue = deque([0])\n",
    "        visited_num = set()\n",
    "        k = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                pos = queue.popleft()\n",
    "                if pos == len(arr) - 1:\n",
    "                    return k\n",
    "                if pos > 0 and pos - 1 not in visited:\n",
    "                    visited.add(pos-1)\n",
    "                    queue.append(pos-1)\n",
    "                if pos < len(arr) - 1 and pos + 1 not in visited:\n",
    "                    visited.add(pos+1)\n",
    "                    queue.append(pos+1)\n",
    "                if arr[pos] not in visited_num:\n",
    "                    visited_num.add(arr[pos])\n",
    "                    for new_pos in d[arr[pos]]:\n",
    "                        if new_pos not in visited:\n",
    "                            visited.add(new_pos)\n",
    "                            queue.append(new_pos)\n",
    "            k += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for idx, num in enumerate(arr):\n",
    "            d[num].append(idx)\n",
    "        visited = {0}\n",
    "        queue = deque([0])\n",
    "        visited_num = set()\n",
    "        k = 0\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                pos = queue.popleft()\n",
    "                if pos == len(arr) - 1:\n",
    "                    return k\n",
    "                if pos > 0 and pos - 1 not in visited:\n",
    "                    visited.add(pos-1)\n",
    "                    queue.append(pos-1)\n",
    "                if pos < len(arr) - 1 and pos + 1 not in visited:\n",
    "                    visited.add(pos+1)\n",
    "                    queue.append(pos+1)\n",
    "                if arr[pos] not in visited_num:\n",
    "                    visited_num.add(arr[pos])\n",
    "                    for new_pos in d[arr[pos]]:\n",
    "                        if new_pos not in visited:\n",
    "                            visited.add(new_pos)\n",
    "                            queue.append(new_pos)\n",
    "            k += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        m = collections.defaultdict(list)\n",
    "        for i, a in enumerate(arr):\n",
    "            m[a].append(i)\n",
    "        \n",
    "        visited_value = collections.defaultdict(int)\n",
    "        visited_node = [False] * len(arr)\n",
    "        q = collections.deque()\n",
    "        q.append(0)\n",
    "        visited_value[arr[0]] = 1\n",
    "        visited_node[0] = True\n",
    "        step = 0\n",
    "        while q:\n",
    "            # print(q)\n",
    "            sz = len(q)\n",
    "            values = set()\n",
    "            for j in range(len(q)):\n",
    "                i = q.popleft()\n",
    "                if i == len(arr)-1:\n",
    "                    return step\n",
    "                for n in [i-1, i+1] + m[arr[i]]:\n",
    "                    if n >= 0 and n < len(arr) and visited_value[arr[n]] < 2 and not visited_node[n]:\n",
    "                        q.append(n)\n",
    "                        values.add(arr[n])\n",
    "                        visited_node[n] = True\n",
    "            for value in values:\n",
    "                visited_value[value] += 1\n",
    "                if visited_value[value] >= 2:\n",
    "                    del m[value]\n",
    "            step += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        g = defaultdict(list)\n",
    "        for i, x in reversed(list(enumerate(arr))):\n",
    "            g[x].append(i)\n",
    "        # BFS\n",
    "        q = deque([0])\n",
    "        steps = [n - 1] * n\n",
    "        steps[0] = 0\n",
    "        while q:\n",
    "            i = q.popleft()\n",
    "            if i == n - 1:\n",
    "                return steps[-1]  \n",
    "            cap = steps[i] + 1\n",
    "            for j in g[arr[i]] + [k for k in [i-1, i+1] if 0<=k<n]:\n",
    "                if steps[j] > cap:\n",
    "                    steps[j] = cap\n",
    "                    q.append(j)   \n",
    "            g.pop(arr[i])    \n",
    "        return steps[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        vis = [False]*n\n",
    "        rec_pos = defaultdict(list)\n",
    "        rec_use = defaultdict(bool)\n",
    "        \n",
    "        for i,num in enumerate(arr):\n",
    "            rec_pos[num].append(i)\n",
    "            rec_use[num] = False\n",
    "\n",
    "        level = 1\n",
    "        q = [0]\n",
    "        dist = [-1]*n\n",
    "        dist[0] = 0\n",
    "        while q:\n",
    "            tmp = q[:]\n",
    "            q = []\n",
    "            for idx in tmp:\n",
    "                if idx-1>=0 and dist[idx-1]==-1:\n",
    "                    dist[idx-1] = level\n",
    "                    q.append(idx-1)\n",
    "                if idx+1<n and dist[idx+1]==-1:\n",
    "                    dist[idx+1] = level\n",
    "                    q.append(idx+1)\n",
    "                if not rec_use[arr[idx]]:\n",
    "                    rec_use[arr[idx]] = True\n",
    "                    for sidx in rec_pos[arr[idx]]:\n",
    "                        if dist[sidx]==-1:\n",
    "                            dist[sidx] = level\n",
    "                            q.append(sidx)\n",
    "            level += 1\n",
    "        return dist[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        # 逐层BFS，计算到达每个位置的最短距离\n",
    "        # 对于操作3，需要记录每个值是否已经用过，避免重复计算\n",
    "        n = len(arr)\n",
    "        vis = [False]*n\n",
    "        rec_pos = defaultdict(list)\n",
    "        rec_use = defaultdict(bool)\n",
    "        \n",
    "        for i,num in enumerate(arr):\n",
    "            rec_pos[num].append(i)\n",
    "            rec_use[num] = False\n",
    "\n",
    "        level = 1\n",
    "        q = [0]\n",
    "        dist = [-1]*n\n",
    "        dist[0] = 0\n",
    "        while q:\n",
    "            tmp = q[:]\n",
    "            q = []\n",
    "            for idx in tmp:\n",
    "                if idx-1>=0 and dist[idx-1]==-1:\n",
    "                    dist[idx-1] = level\n",
    "                    q.append(idx-1)\n",
    "                if idx+1<n and dist[idx+1]==-1:\n",
    "                    dist[idx+1] = level\n",
    "                    q.append(idx+1)\n",
    "                if not rec_use[arr[idx]]:\n",
    "                    rec_use[arr[idx]] = True\n",
    "                    for sidx in rec_pos[arr[idx]]:\n",
    "                        if dist[sidx]==-1:\n",
    "                            dist[sidx] = level\n",
    "                            q.append(sidx)\n",
    "            level += 1\n",
    "        return dist[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        d=defaultdict(list)\n",
    "        for i,v in enumerate(arr):\n",
    "            d[v].append(i)\n",
    "        que=[0]\n",
    "        res = 0\n",
    "        visited=set()\n",
    "        jumped = set()\n",
    "        while que:\n",
    "            tmp = []\n",
    "            for q in que:\n",
    "                if q==len(arr)-1:\n",
    "                    return res\n",
    "                if q in visited:\n",
    "                    continue\n",
    "                visited.add(q)\n",
    "                toJump = []\n",
    "                if arr[q] not in jumped:\n",
    "                    jumped.add(arr[q])\n",
    "                    toJump = d[arr[q]]\n",
    "                for nxt in [q+1,q-1]+toJump:\n",
    "                    if 0<=nxt<len(arr):\n",
    "                        tmp.append(nxt)\n",
    "            que = tmp\n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "class Solution:\n",
    "    def minJumps(self, arr):\n",
    "        data0 = {}\n",
    "        for ind, val in enumerate(arr):\n",
    "            if val not in data0:\n",
    "                data0[val] = set()\n",
    "            data0[val].add(ind)\n",
    "        queue = Queue()\n",
    "        error = set([0])\n",
    "        queue.put([0,0])\n",
    "        while not queue.empty():\n",
    "            data = queue.get() \n",
    "            if data[0] == len(arr) - 1:\n",
    "                return data[1]\n",
    "            if arr[data[0] + 1 ] in data0:\n",
    "                queue.put([data[0] + 1,data[1] + 1])\n",
    "            if data[0] - 1 > 0 and arr[data[0] - 1] in data0:\n",
    "                queue.put([data[0] - 1,data[1] + 1])\n",
    "            if arr[data[0]] in data0:\n",
    "                for va in data0[arr[data[0]]]:\n",
    "                    if va != data[0]:\n",
    "                        queue.put([va,data[1] + 1])\n",
    "                del data0[arr[data[0]]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        if len(arr) == 1:\n",
    "            return 0\n",
    "        if len(arr) == len(set(arr)):\n",
    "            return len(arr) - 1\n",
    "        a, b, c, d = set(), set(), set(), set()\n",
    "        li, z = {}, 0\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] not in li:\n",
    "                li[arr[i]] = [i]\n",
    "            else:\n",
    "                tmp = li[arr[i]]\n",
    "                tmp.append(i)\n",
    "                li[arr[i]] = tmp\n",
    "        b.add(0)\n",
    "        a.add(0)\n",
    "        while 1:\n",
    "            c.update(each - 1 for each in b)\n",
    "            c.update(each + 1 for each in b)\n",
    "            for each in b:\n",
    "                if each not in d:\n",
    "                    d.update(li[arr[each]])\n",
    "            c = c | d\n",
    "            d.clear()\n",
    "            if -1 in c:\n",
    "                c.remove(-1)\n",
    "            z += 1\n",
    "            if (len(arr) - 1) in c:\n",
    "                return z\n",
    "            b = c - a\n",
    "            a = a | c\n",
    "            c.clear()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        pos_map, visited, q, n, visited_idx = defaultdict(list), set(), deque(), len(arr), set()\n",
    "        for i, num in enumerate(arr):\n",
    "            pos_map[num].append(i)\n",
    "        q.append((0, 0))\n",
    "        visited_idx.add(0)\n",
    "        while q:\n",
    "            cur_idx, steps = q[0]\n",
    "            q.popleft()\n",
    "            if cur_idx == n - 1: return steps\n",
    "            if arr[cur_idx] not in visited:\n",
    "                for idx in pos_map[arr[cur_idx]]:\n",
    "                    if idx not in visited_idx: \n",
    "                        q.append((idx, steps + 1))\n",
    "                        visited_idx.add(idx)\n",
    "                visited.add(arr[cur_idx])\n",
    "            if cur_idx - 1 >= 0 and arr[cur_idx - 1] not in visited:\n",
    "                if cur_idx - 1 not in visited_idx: \n",
    "                    q.append((cur_idx - 1, steps + 1))\n",
    "                    visited_idx.add(cur_idx - 1)\n",
    "            if cur_idx + 1 < n and arr[cur_idx + 1] not in visited:\n",
    "                if cur_idx + 1 not in visited_idx:\n",
    "                    q.append((cur_idx + 1, steps + 1))\n",
    "                    visited_idx.add(cur_idx + 1)\n",
    "        return -1\n",
    "\n",
    "\n",
    "# TLE:\n",
    "    # def minJumps(self, arr: List[int]) -> int:\n",
    "    #     pos_map, visited, q, n = defaultdict(list), set(), deque(), len(arr)\n",
    "    #     for i, num in enumerate(arr):\n",
    "    #         pos_map[num].append(i)\n",
    "    #     q.append((0, 0))\n",
    "    #     while q:\n",
    "    #         cur_idx, steps = q[0]\n",
    "    #         q.popleft()\n",
    "    #         if cur_idx == n - 1: return steps\n",
    "    #         if arr[cur_idx] not in visited:\n",
    "    #             for idx in pos_map[arr[cur_idx]]:\n",
    "    #                 q.append((idx, steps + 1))\n",
    "    #             visited.add(arr[cur_idx])\n",
    "    #         if cur_idx - 1 >= 0 and arr[cur_idx - 1] not in visited:\n",
    "    #             q.append((cur_idx - 1, steps + 1))\n",
    "    #         if cur_idx + 1 < n and arr[cur_idx + 1] not in visited:\n",
    "    #             q.append((cur_idx + 1, steps + 1))\n",
    "    #     return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "\n",
    "        if len(arr)==1:\n",
    "            return 0\n",
    "        sames = collections.defaultdict(set)\n",
    "        for i in reversed(range(len(arr))):\n",
    "            sames[arr[i]].add(i)\n",
    "        if len(sames)==len(arr):return len(arr)-1\n",
    "        visited = set()\n",
    "        def move(i):\n",
    "            if arr[i] in sames:\n",
    "                for j in sames.pop(arr[i]):\n",
    "                    visited.add(j)\n",
    "                    if j!=i:\n",
    "                        yield j\n",
    "            if i!=len(arr)-1 and i+1 not in visited:\n",
    "                # visited.add(i+1)\n",
    "                yield i+1\n",
    "            if i!=0 and i-1 not in visited:\n",
    "                # visited.add(i-1)\n",
    "                yield i-1\n",
    "        BFS = set([0])\n",
    "        count = 0\n",
    "        while(BFS):\n",
    "            if len(arr)-1 in BFS:return count\n",
    "            BNext = set()\n",
    "            for i in BFS:\n",
    "                BNext.update(move(i))\n",
    "            BFS = BNext\n",
    "            count +=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        # O(n) 广度优先\n",
    "        n = len(arr)\n",
    "        if n == 1: return 0\n",
    "        numToIndex = defaultdict(list)\n",
    "        for i, num in enumerate(arr):\n",
    "            numToIndex[num].append(i)\n",
    "        vis = set()\n",
    "        vis_num = set()\n",
    "        vis.add(0)\n",
    "        q = [0]  #\n",
    "        count = 0 \n",
    "        while q:\n",
    "            count += 1\n",
    "            ter = []\n",
    "            for x in q:\n",
    "                if x-1 == n-1 or x+1 == n-1: return count\n",
    "                if x-1 >= 0 and x-1 not in vis:\n",
    "                    vis.add(x-1) \n",
    "                    ter.append(x-1)\n",
    "                if x+1 <= n-1 and x+1 not in vis:\n",
    "                    vis.add(x+1)\n",
    "                    ter.append(x+1)\n",
    "                if arr[x] in vis_num: continue\n",
    "                for new in numToIndex[arr[x]]:\n",
    "                    if new == n-1: return count\n",
    "                    if new not in vis:\n",
    "                        ter.append(new)\n",
    "                        vis.add(new)\n",
    "                vis_num.add(arr[x])\n",
    "            q = ter\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        from collections import defaultdict, deque\n",
    "        d = defaultdict(set)\n",
    "        for i, a in enumerate(arr):\n",
    "            d[arr[i]].add(i)\n",
    "        \n",
    "        #BFS /Dijstra 直接的会超时 原因在于相同的元素太多, 在访问过一个位置之后，就应该把d[arr[i]]清空\n",
    "        #因为arr[i]的所有j都已经入队,对于j来说，不应该再把d[arr[i]]继续遍历一笔\n",
    "        q = deque([(0, 0)])#steps, node\n",
    "        visited = [False]*n \n",
    "        ans = -1\n",
    "        while q:\n",
    "            ans, i = q.popleft()\n",
    "            visited[i] = True\n",
    "            if i==n-1:\n",
    "                break\n",
    "            \n",
    "            for j in [i-1, i+1, *d[arr[i]]]:\n",
    "                if j<0 or j>=n or j==i: continue\n",
    "                if not visited[j]:\n",
    "                    q.append((ans+1, j))\n",
    "            d[arr[i]] = set()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        d = {}\n",
    "        for i, a in enumerate(arr):\n",
    "            if a not in d:\n",
    "                d[a] = []\n",
    "            d[a].append(i)\n",
    "        n = len(arr)\n",
    "        steps = {i: n for i in range(n)}\n",
    "        steps[n-1] = 0\n",
    "        tmp = [n-1]\n",
    "        for i in range(n-1):\n",
    "            new_tmp = []\n",
    "            for t in tmp:\n",
    "                v = arr[t]\n",
    "                if v in d:\n",
    "                    tos = d[v]\n",
    "                    d.pop(v)\n",
    "                    for to in tos:\n",
    "                        if to == t:\n",
    "                            continue\n",
    "                        if steps[to] > steps[t] + 1:\n",
    "                            steps[to] = steps[t] + 1\n",
    "                            new_tmp.append(to)\n",
    "                if t + 1 <= n-1:\n",
    "                    if steps[t+1] > steps[t] + 1:\n",
    "                        steps[t+1] = steps[t] + 1\n",
    "                        new_tmp.append(t+1)\n",
    "                if t - 1 >= 0:\n",
    "                    if steps[t-1] > steps[t] + 1:\n",
    "                        steps[t-1] = steps[t] + 1\n",
    "                        new_tmp.append(t-1)\n",
    "            tmp = new_tmp\n",
    "        return steps[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        from collections import defaultdict, deque\n",
    "        d = defaultdict(set)\n",
    "        for i, a in enumerate(arr):\n",
    "            d[arr[i]].add(i)\n",
    "        \n",
    "        #BFS /Dijstra 直接的会超时 原因在于相同的元素太多, 在访问过一个位置之后，就应该把d[arr[i]]清空\n",
    "        #因为arr[i]的所有j都已经入队,对于j来说，不应该再把d[arr[i]]继续遍历一笔\n",
    "        q = deque([(0, 0)])#steps, node\n",
    "        visited = [False]*n \n",
    "        ans = -1\n",
    "        while q:\n",
    "            ans, i = q.popleft()\n",
    "            visited[i] = True\n",
    "            if i==n-1:\n",
    "                break\n",
    "            \n",
    "            for j in [i-1, i+1, *d[arr[i]]]:\n",
    "                if j<0 or j>=n or j==i: continue\n",
    "                if not visited[j]:\n",
    "                    q.append((ans+1, j))\n",
    "            del d[arr[i]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        edges = defaultdict(set)\n",
    "        flags = [0] * len(arr)\n",
    "        flags[0] = 1\n",
    "        # paths = [0] * len(arr)\n",
    "        for (idx, num) in enumerate(arr):\n",
    "            edges[num].add(idx)\n",
    "        q = [0]\n",
    "        step = 0\n",
    "        while q:\n",
    "            step += 1\n",
    "            next_q = []\n",
    "            for current in q:\n",
    "                for diff in -1, 1:\n",
    "                    if 0 <= current + diff < len(arr) and flags[current + diff] == 0:\n",
    "                        if current + diff == len(arr) - 1:\n",
    "                            return step\n",
    "                        flags[current + diff] = 1\n",
    "                        next_q.append(current + diff)\n",
    "                for neighbor in edges[arr[current]]:\n",
    "                    if flags[neighbor] == 0:\n",
    "                        if neighbor == len(arr) - 1:\n",
    "                            return step\n",
    "                        flags[neighbor] = 1\n",
    "                        next_q.append(neighbor)\n",
    "                del edges[arr[current]]\n",
    "            q = next_q\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        if len(arr) == 1:\n",
    "            return 0\n",
    "        dic_map = {}\n",
    "        for pos, nums in enumerate(arr):\n",
    "            if nums not in dic_map:\n",
    "                dic_map[nums] = []\n",
    "            dic_map[nums].append(pos)\n",
    "        times = 0\n",
    "        already_go = {0:None}\n",
    "        next_go = [0]\n",
    "        already_go_value = {}\n",
    "        while True:\n",
    "            next_step = []\n",
    "            times += 1\n",
    "            for every_where in next_go:\n",
    "                temp_list = self.get_where_can_go(every_where,dic_map, already_go,arr, already_go_value)\n",
    "                if len(arr)-1 in temp_list:\n",
    "                    return times\n",
    "                next_step.extend(temp_list)\n",
    "            next_step.reverse()\n",
    "            next_go = next_step\n",
    "            \n",
    "        return times\n",
    "\n",
    "    def get_where_can_go(self, pos, dic_map, already_go, arr, already_go_value):\n",
    "        go_list = []\n",
    "        if pos > 0 and pos - 1 not in already_go:\n",
    "            go_list.append(pos - 1)\n",
    "            already_go[pos - 1] = None\n",
    "        if pos < len(arr) and pos + 1 not in already_go:\n",
    "            go_list.append(pos + 1)\n",
    "            already_go[pos + 1] = None\n",
    "        if arr[pos] not in already_go_value:\n",
    "            already_go_value[arr[pos]] = None\n",
    "            for each in dic_map[arr[pos]]:\n",
    "                if each != pos and each not in already_go:\n",
    "                    go_list.append(each)\n",
    "                    already_go[each] = None\n",
    "        return go_list   \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        idxSameValue = defaultdict(list)\n",
    "        for i, a in enumerate(arr):\n",
    "            idxSameValue[a].append(i)\n",
    "        \n",
    "        visitedIndex = set()\n",
    "        q = deque()\n",
    "        q.append([0, 0])\n",
    "        \n",
    "        visitedIndex.add(0)\n",
    "        visitedvalue = set()\n",
    "        visitedvalue.add(0)\n",
    "        while q :\n",
    "            idx, step = q.popleft()\n",
    "            if idx == len(arr) - 1:\n",
    "                return step\n",
    "            \n",
    "            v = arr[idx]\n",
    "            step += 1\n",
    "            \n",
    "            for i in idxSameValue[v]:\n",
    "                if v in visitedvalue:\n",
    "                    break\n",
    "                if i not in visitedIndex:\n",
    "                    visitedIndex.add(i)\n",
    "                    q.append([i, step])\n",
    "            visitedvalue.add(v)\n",
    "            \n",
    "            if idx + 1 < len(arr) and (idx + 1) not in visitedIndex:\n",
    "                visitedIndex.add(idx + 1)\n",
    "                q.append([idx+1, step])\n",
    "            if idx - 1 >= 0 and (idx - 1) not in visitedIndex:\n",
    "                visitedIndex.add(idx - 1)\n",
    "                q.append([idx-1, step])\n",
    "            \n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        index = defaultdict(set)\n",
    "        for i, n in enumerate(arr):\n",
    "            index[n].add(i)\n",
    "        q = [0]\n",
    "        ans = 0\n",
    "        index[arr[0]].remove(0)\n",
    "        while q:\n",
    "            tmp = []\n",
    "            for i in q:\n",
    "                if i == len(arr) - 1: return ans\n",
    "                if i + 1 < len(arr):\n",
    "                    n = arr[i + 1]\n",
    "                    if i + 1 in index[n]:\n",
    "                        index[n].remove(i + 1)\n",
    "                        tmp.append(i + 1)\n",
    "                if i > 0:\n",
    "                    n = arr[i - 1]\n",
    "                    if i - 1 in index[n]:\n",
    "                        index[n].remove(i - 1)\n",
    "                        tmp.append(i - 1)\n",
    "                for j in index[arr[i]]:\n",
    "                    tmp.append(j)\n",
    "                index[arr[i]].clear()\n",
    "            ans += 1\n",
    "            q = tmp\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        idxSameValue = defaultdict(list)\n",
    "        for i, a in enumerate(arr):\n",
    "            idxSameValue[a].append(i)\n",
    "        \n",
    "        visitedIndex = set()\n",
    "        q = deque()\n",
    "        q.append([0, 0])\n",
    "        \n",
    "        visitedIndex.add(0)\n",
    "        visitedvalue = set()\n",
    "        visitedvalue.add(0)\n",
    "        while q :\n",
    "            idx, step = q.popleft()\n",
    "            if idx == len(arr) - 1:\n",
    "                return step\n",
    "            \n",
    "            v = arr[idx]\n",
    "            step += 1\n",
    "            \n",
    "            for i in idxSameValue[v]:\n",
    "                if v in visitedvalue:\n",
    "                    break\n",
    "                if i not in visitedIndex:\n",
    "                    visitedIndex.add(i)\n",
    "                    q.append([i, step])\n",
    "            visitedvalue.add(v)\n",
    "            \n",
    "            if idx + 1 < len(arr) and (idx + 1) not in visitedIndex:\n",
    "                visitedIndex.add(idx + 1)\n",
    "                q.append([idx+1, step])\n",
    "            if idx - 1 >= 0 and (idx - 1) not in visitedIndex:\n",
    "                visitedIndex.add(idx - 1)\n",
    "                q.append([idx-1, step])\n",
    "            \n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        ad=collections.defaultdict(set)\n",
    "        for i,v in enumerate(arr):\n",
    "            ad[v].add(i)\n",
    "        n=len(arr)\n",
    "        vis=[0]*n\n",
    "        stack=collections.deque()\n",
    "        stack.append((0,0))\n",
    "        vis[0]=1\n",
    "        while stack:\n",
    "            cur,d =stack.popleft()\n",
    "          #  if vis[cur]==1:\n",
    "           #     continue\n",
    "          #  vis[cur]=1\n",
    "            if cur==(n-1):\n",
    "                return d\n",
    "            for nex in (cur+1,cur-1):\n",
    "                if 0<=nex<n and vis[nex]==0:\n",
    "                    vis[nex]=1\n",
    "                    stack.append((nex,d+1))\n",
    "\n",
    "            for nex in ad[arr[cur]]:\n",
    "               # print(ad[arr[cur]])\n",
    "              #  print(nex)\n",
    "                if 0<=nex<n and vis[nex]==0:\n",
    "                    vis[nex]=1\n",
    "                    stack.append((nex,d+1))\n",
    "            ad[arr[cur]]=set()\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        vis = [False] * n\n",
    "        m = {}\n",
    "        for i, x in enumerate(arr):\n",
    "            if x in m:\n",
    "                m[x].add(i)\n",
    "            else:\n",
    "                m[x] = set()\n",
    "                m[x].add(i)\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        vis[0] = True\n",
    "        step = 0\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            # print(\"q:\"+ str(q)+\",step:\"+str(step))\n",
    "            for _ in range(size):\n",
    "                i = q.popleft()\n",
    "                x = arr[i]\n",
    "                if i == n - 1:\n",
    "                    # print(\"i:\" + str(i) + \",n - 1:\"+ str(n - 1))\n",
    "                    return step\n",
    "                for y in i - 1, i + 1:\n",
    "                    if 0 <= y and y < n and not vis[y]:\n",
    "                        vis[y] = True\n",
    "                        q.append(y)\n",
    "                for y in m[x]:\n",
    "                    if not vis[y]:\n",
    "                        vis[y] = True\n",
    "                        q.append(y)\n",
    "                m[x] = set()\n",
    "            step += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        vis = [False] * n\n",
    "        m = defaultdict(set)\n",
    "        for i, x in enumerate(arr):\n",
    "            m[x].add(i)\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        vis[0] = True\n",
    "        step = 0\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            # print(\"q:\"+ str(q)+\",step:\"+str(step))\n",
    "            for _ in range(size):\n",
    "                i = q.popleft()\n",
    "                x = arr[i]\n",
    "                if i == n - 1:\n",
    "                    # print(\"i:\" + str(i) + \",n - 1:\"+ str(n - 1))\n",
    "                    return step\n",
    "                for y in i - 1, i + 1:\n",
    "                    if 0 <= y and y < n and not vis[y]:\n",
    "                        vis[y] = True\n",
    "                        q.append(y)\n",
    "                for y in m[x]:\n",
    "                    if not vis[y]:\n",
    "                        vis[y] = True\n",
    "                        q.append(y)\n",
    "                m[x] = set()\n",
    "            step += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        # 广度优先搜索，返回最短路径\n",
    "        # 建图\n",
    "        g = defaultdict(set)\n",
    "        for i,num in enumerate(arr):\n",
    "            g[num].add(i)\n",
    "        # 试试双向BFS\n",
    "        \n",
    "        l = set()\n",
    "        r = set()\n",
    "        l.add((arr[0], 0))\n",
    "        r.add((arr[-1], len(arr)-1))\n",
    "        use = set()\n",
    "        use.add(0)\n",
    "        use.add(len(arr)-1)\n",
    "        cnt = 0\n",
    "        while l and r :\n",
    "            if len(l) > len(r): l, r = r, l # 让l保持最小\n",
    "            temp = set()\n",
    "            for node,index in l:\n",
    "                if (node, index) in r: return cnt \n",
    "                for nxt in g[node]:\n",
    "                    if nxt != index:\n",
    "                        if (node, nxt) in r: return cnt + 1\n",
    "                        if nxt not in use:\n",
    "                            use.add(nxt)\n",
    "                            temp.add((node, nxt))\n",
    "                del g[node]\n",
    "                for nxt in [index-1, index+1]:\n",
    "                    if 0 <= nxt < len(arr):\n",
    "                        if (arr[nxt], nxt) in r: return cnt + 1\n",
    "                        if nxt not in use:\n",
    "                            use.add(nxt)\n",
    "                            temp.add((arr[nxt], nxt))\n",
    "            l = temp\n",
    "            cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        from collections import deque\n",
    "        queue=deque()\n",
    "        process=set()\n",
    "        queue.append([0,0])\n",
    "        process.add(0)\n",
    "        n=len(arr)\n",
    "\n",
    "        nums={}\n",
    "        nums = {}\n",
    "        for i in range(n):\n",
    "            if arr[i] not in nums:\n",
    "                nums[arr[i]]={i}\n",
    "            else:\n",
    "                nums[arr[i]].add(i)\n",
    "        while queue:\n",
    "            a,step=queue.popleft()\n",
    "            if a==n-1:\n",
    "                return step\n",
    "            if arr[a] in nums:\n",
    "                b={a+1,a-1}|nums[arr[a]]\n",
    "                del nums[arr[a]]\n",
    "            else:\n",
    "                b={a+1,a-1}\n",
    "            step+=1\n",
    "            for j in b:\n",
    "                if 0<=j<n and j not in process:\n",
    "                    process.add(j)\n",
    "                    queue.append([j,step])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        q = collections.deque([(0, 0)])\n",
    "        visited = set()\n",
    "        val_to_idx = collections.defaultdict(list)  # val -> index\n",
    "        for i in range(n-1, -1, -1):\n",
    "            v = arr[i]\n",
    "            # if len(val_to_idx[v]) >= 2 and val_to_idx[v][-1] + 1 == val_to_idx[v][-2] and val_to_idx[v][-1] == i + 1:\n",
    "            #     val_to_idx[v][-1] = i\n",
    "            # else:\n",
    "            #     val_to_idx[v].append(i)\n",
    "            val_to_idx[v].append(i)\n",
    "\n",
    "        while q:\n",
    "            cur, step = q.popleft()\n",
    "            if cur == n-1:\n",
    "                return step\n",
    "            v = arr[cur]\n",
    "            for nx in val_to_idx[v]:\n",
    "                if nx in visited:\n",
    "                    continue\n",
    "                if nx == n-1:\n",
    "                    return step+1\n",
    "                visited.add(nx)\n",
    "                q.append((nx, step+1))\n",
    "            val_to_idx.pop(v)\n",
    "            \n",
    "                \n",
    "            for nx in [cur - 1, cur + 1] + val_to_idx[arr[cur]]:\n",
    "                if cur == nx or nx < 0 or nx >= n or nx in visited:\n",
    "                    continue\n",
    "                if nx == n-1:\n",
    "                    return step+1\n",
    "                visited.add(nx)\n",
    "                q.append((nx, step+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "def dijkstra(arr, d, n, s, e=None):\n",
    "    # 节点范围 0 ~ n-1\n",
    "    # 求源点 s 到任意点的距离\n",
    "    # 先初始化好 dist, visited, 后面只会更新 dist 和 visited\n",
    "    # dist[i] 表示 s-i 的距离\n",
    "    dist = [float(\"inf\")] * n\n",
    "    dist[s] = 0\n",
    "    visited = set()\n",
    "    vs = set() # visited value\n",
    "    queue = deque([(0, s)]) # (p, idx)\n",
    "    while queue:\n",
    "        di, idx = queue.popleft()\n",
    "        if idx == e:\n",
    "            return di\n",
    "        visited.add(idx)\n",
    "        # 通过 idx 更新与它相连的点, s-idx-p < s-p\n",
    "        v = arr[idx]\n",
    "        ps = [idx+1, idx-1]\n",
    "        if v not in vs:\n",
    "            ps.extend(d[v])\n",
    "        for p in ps:\n",
    "            if not 0<=p<n and p!=idx: continue\n",
    "            if p==e:\n",
    "                return di+1\n",
    "            if p not in visited and dist[idx] + 1 < dist[p]:\n",
    "                dist[p] = dist[idx] + 1\n",
    "                queue.append((dist[p], p))\n",
    "        vs.add(v)\n",
    "    return dist\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        d = defaultdict(list) # value: [idxs]\n",
    "        for i, v in enumerate(arr):\n",
    "            d[v].append(i)\n",
    "        return dijkstra(arr, d, n, 0, n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        same_points = defaultdict(set)\n",
    "        for i, n in enumerate(arr):\n",
    "            same_points[n].add(i)\n",
    "        q = {0}\n",
    "        checked = set()\n",
    "        target = len(arr)-1\n",
    "        loop = 0\n",
    "        while q and target not in q:\n",
    "            checked |= q\n",
    "            new_q = set()\n",
    "            for i in q:\n",
    "                same_points[arr[i]].remove(i)\n",
    "            for i in q:\n",
    "                if i-1 >= 0:\n",
    "                    new_q.add(i-1)\n",
    "                if i+1 <= target:\n",
    "                    new_q.add(i+1)\n",
    "                new_q |= same_points[arr[i]]\n",
    "            q = new_q - checked\n",
    "            loop += 1\n",
    "        return loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        d = defaultdict(set)\n",
    "        for i, x in enumerate(arr):\n",
    "            d[x].add(i)\n",
    "        \n",
    "        q = deque([[0, 0]])\n",
    "        vis = {0, }\n",
    "        while q:\n",
    "            i, step = q.popleft()           \n",
    "            if i == n - 1: return step\n",
    "            v = d[arr[i]]\n",
    "            v.add(i+1)\n",
    "            if i: v.add(i-1)\n",
    "            for j in v:\n",
    "                if j not in vis:\n",
    "                    q.append([j, step + 1])\n",
    "                    vis.add(j)\n",
    "            d.pop(arr[i])\n",
    "            \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "###### 1.(为节省时间) 调整visited让已经到达的就不要出发新的节点了\n",
    "###### 2.(为节省空间) 对于已经处理过的dic也删空\n",
    "class Solution:  ###### 现在这个版本是 超出内存限制\n",
    "    ###### 一维BFS的模版\n",
    "    def bfs(self, arr, start, ntime, visited, dic): #### 增加一个参数（已经达到过得）\n",
    "        len_arr = len(arr)\n",
    "        arr_list = [[start, ntime]]\n",
    "        while arr_list:\n",
    "            add_list = []\n",
    "            for pos,ntime in arr_list:\n",
    "                if (0 <= pos < len_arr) and visited[pos] == float(\"inf\"):\n",
    "                    visited[pos] = ntime \n",
    "                    if pos == (len_arr-1): return ntime \n",
    "                    ###### 添加新位置的可能一 \n",
    "                    add_list += [[pos+1, ntime+1], [pos-1, ntime+1]]\n",
    "                    ###### 添加新位置的可能二\n",
    "                    for element in dic[arr[pos]]:\n",
    "                        if visited[element] == float(\"inf\"):\n",
    "                            add_list += [[element, ntime+1]]\n",
    "                    dic[arr[pos]] = []\n",
    "            arr_list = add_list\n",
    "        return 0\n",
    "    def minJumps(self, arr: List[int]) -> bool:\n",
    "        len_arr = len(arr)\n",
    "        visited = [float(\"inf\")] * len_arr\n",
    "        dic = collections.defaultdict(list)\n",
    "        for i in range(len_arr): dic[arr[i]].append(i)\n",
    "\n",
    "        res = self.bfs(arr, 0, 0, visited, dic)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        # 广度优先搜索，返回最短路径\n",
    "        # 建图\n",
    "        g = defaultdict(set)\n",
    "        for i,num in enumerate(arr):\n",
    "            g[num].add(i)\n",
    "        # 先看广搜能不能过\n",
    "        queue = deque()\n",
    "        queue.append((arr[0], 0))\n",
    "        use = set()\n",
    "        use.add(0)\n",
    "        cnt = 0\n",
    "        vis = set()\n",
    "        while queue:\n",
    "            n  = len(queue)\n",
    "            for _ in range(n):\n",
    "                node, index = queue.popleft()\n",
    "                if index == len(arr)-1: return cnt \n",
    "                for i in g[node]: \n",
    "                    if i!=index and i not in use:\n",
    "                        use.add(i) \n",
    "                        queue.append((node, i))\n",
    "                del g[node]\n",
    "                for i in [index-1, index+1]:\n",
    "                    if 0 <= i < len(arr) and i not in use:\n",
    "                        use.add(i)\n",
    "                        queue.append((arr[i], i))\n",
    "            \n",
    "            cnt += 1\n",
    "        return cnt\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        length = len(arr)\n",
    "        for i in range(length):\n",
    "            g[arr[i]].add(i)\n",
    "        visited = set()\n",
    "        queue = {0}\n",
    "        step = 0\n",
    "        while queue:\n",
    "            next_queue = set()\n",
    "            while queue:\n",
    "                index = queue.pop()\n",
    "                if index == length - 1:\n",
    "                    return step\n",
    "                visited.add(index)\n",
    "                num = arr[index]\n",
    "                for i in g[num]:\n",
    "                    if i not in visited:\n",
    "                        next_queue.add(i)\n",
    "                del g[num]\n",
    "                if index + 1 < length and index + 1 not in visited:\n",
    "                    next_queue.add(index + 1)\n",
    "                if index - 1 >= 0 and index - 1 not in visited:\n",
    "                    next_queue.add(index - 1)\n",
    "            queue = next_queue\n",
    "            step += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "from math import inf\n",
    "from typing import List\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        v_map=defaultdict(set)\n",
    "        for i,v in enumerate(arr):\n",
    "            v_map[v].add(i)\n",
    "        s=[inf]*len(arr)\n",
    "        s[0]=0\n",
    "        q=queue.deque([0])\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            for _ in range(size):\n",
    "                index=q.popleft()\n",
    "                if index+1<len(arr) and s[index+1]==inf:\n",
    "                    s[index+1]=s[index]+1\n",
    "                    q.append(index+1)\n",
    "                if index-1>=0 and s[index-1]==inf:\n",
    "                    s[index-1]=s[index]+1\n",
    "                    q.append(index-1)\n",
    "                t=set()\n",
    "                for to in v_map[arr[index]]:\n",
    "                    if to==index:\n",
    "                        continue\n",
    "                    if s[to]==inf:\n",
    "                        s[to]=s[index]+1\n",
    "                        t.add(to)\n",
    "                        q.append(to)\n",
    "                v_map[arr[index]].difference_update(t)\n",
    "        return s[-1]\n",
    "if __name__ == '__main__':\n",
    "    Solution().minJumps([100,-23,-23,404,100,23,23,23,3,404])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        from collections import deque\n",
    "\n",
    "        dic = defaultdict(set)\n",
    "\n",
    "        for i,num in enumerate(arr):\n",
    "            dic[num].add(i)\n",
    "\n",
    "        visited = set()\n",
    "\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        visited.add(0)\n",
    "        dis = [0 for i in range(len(arr))]\n",
    "\n",
    "        if len(arr) == 1:\n",
    "            return 0\n",
    "        \n",
    "        depth = 0\n",
    "\n",
    "        while q:\n",
    "            index = q.popleft()\n",
    "            dist = dis[index]\n",
    "            \n",
    "            if index == len(arr)-1:\n",
    "                return dist\n",
    "            \n",
    "            if index - 1 >=0 and index-1 not in visited:\n",
    "                q.append(index-1)\n",
    "                visited.add(index-1)\n",
    "                dis[index-1] = dist + 1\n",
    "            if index + 1 <len(arr) and index + 1 not in visited:\n",
    "                q.append(index+1)\n",
    "                visited.add(index+1)\n",
    "                dis[index+1] = dist + 1\n",
    "                    \n",
    "            for next_index in dic[arr[index]]:\n",
    "                if next_index not in visited:\n",
    "                    q.append(next_index)\n",
    "                    visited.add(next_index)\n",
    "                    dis[next_index] = dist + 1\n",
    "            dic.pop(arr[index])\n",
    "\n",
    "        return dis[-1]\n",
    "                \n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        from collections import deque\n",
    "\n",
    "        dic = defaultdict(set)\n",
    "\n",
    "        for i,num in enumerate(arr):\n",
    "            dic[num].add(i)\n",
    "\n",
    "        visited = set()\n",
    "\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        visited.add(0)\n",
    "        dis = [0 for i in range(len(arr))]\n",
    "\n",
    "        if len(arr) == 1:\n",
    "            return 0\n",
    "        \n",
    "        depth = 0\n",
    "\n",
    "        while q:\n",
    "            index = q.popleft()\n",
    "            dist = dis[index]\n",
    "            \n",
    "            if index == len(arr)-1:\n",
    "                return dist\n",
    "            \n",
    "            if index - 1 >=0 and index-1 not in visited:\n",
    "                q.append(index-1)\n",
    "                visited.add(index-1)\n",
    "                dis[index-1] = dist + 1\n",
    "            if index + 1 <len(arr) and index + 1 not in visited:\n",
    "                q.append(index+1)\n",
    "                visited.add(index+1)\n",
    "                dis[index+1] = dist + 1\n",
    "                    \n",
    "            for next_index in dic[arr[index]]:\n",
    "                if next_index not in visited:\n",
    "                    q.append(next_index)\n",
    "                    visited.add(next_index)\n",
    "                    dis[next_index] = dist + 1\n",
    "            dic.pop(arr[index])\n",
    "\n",
    "        return dis[-1]\n",
    "                \n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        value_flag_dict = {}\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        dict_index = {}\n",
    "        for index, one in enumerate(arr):\n",
    "            if one in dict_index.keys():\n",
    "                dict_index[one].add(index)\n",
    "            else:\n",
    "                dict_index[one] = set()\n",
    "                dict_index[one].add(index)\n",
    "        \n",
    "        for key in dict_index.keys():\n",
    "            value_flag_dict[key] = False\n",
    "\n",
    "        # 初始化\n",
    "        value_flag_dict[arr[-1]] = True\n",
    "        \n",
    "        candidate = set(dict_index[arr[-1]])\n",
    "        candidate.remove(n-1)\n",
    "        candidate.add(n-2)\n",
    "        step = 1\n",
    "        list_2 = set()\n",
    "        while True:\n",
    "            for one in candidate:\n",
    "                if one == 0:\n",
    "                    return step\n",
    "\n",
    "                if value_flag_dict[arr[one]]:\n",
    "                    tmp1 = set()\n",
    "                else:\n",
    "                    tmp1 = set(dict_index[arr[one]])\n",
    "                    tmp1.remove(one)\n",
    "                if one - 1 >= 0 and value_flag_dict[arr[one-1]] == False:\n",
    "                    tmp1.add(one-1)\n",
    "                if one + 1 < n and value_flag_dict[arr[one+1]] == False:\n",
    "                    tmp1.add(one + 1)\n",
    "                list_2.update(tmp1)\n",
    "                value_flag_dict[arr[one]] = True\n",
    "            step += 1\n",
    "            candidate = list_2\n",
    "            list_2 = set()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minJumps(self, arr: List[int]) -> int:\n",
    "        vis = {}\n",
    "        visval = {}\n",
    "        nxt = {}\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            if arr[i] in nxt:\n",
    "                nxt[arr[i]].append(i)\n",
    "            else:\n",
    "                nxt[arr[i]] = [i]\n",
    "        q = deque()\n",
    "        q.append((0, 0))\n",
    "        vis[0] = 1\n",
    "        while q:\n",
    "            idx, step = q.popleft()\n",
    "            if idx == n-1:\n",
    "                return step\n",
    "            if idx - 1 >= 0 and vis.get(idx-1, 0) == 0:\n",
    "                vis[idx - 1] = 1\n",
    "                q.append((idx - 1, step + 1))\n",
    "            if idx + 1 < n and vis.get(idx+1, 0) == 0:\n",
    "                vis[idx + 1] = 1\n",
    "                q.append((idx + 1, step + 1))\n",
    "            if arr[idx] in nxt and visval.get(arr[idx], 0) == 0:\n",
    "                visval[arr[idx]] = 1\n",
    "                for x in nxt[arr[idx]]:\n",
    "                    if vis.get(x, 0) == 0:\n",
    "                        vis[x] = 1\n",
    "                        q.append((x, step + 1))\n",
    "                \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
